Ch.3 Linear Geometry

Return to TOC

Linear Geometry

Draw two unknown equations as lines, then three possibilities arise:

Unique Solution

No Solutions

Infinitely Many Solutions

---

Vectors

object with magnitude and direction; models displacement
vectors are equal iff same magnitude and same direction

Vector going from $(a_1,a_2,...,a_n)$ to $(b_1,b_2,...,b_n)$ is
$\begin{pmatrix}b_1-a_1\\b_2-a_2\\\vdots\\b_n-a_n\end{pmatrix}=\begin{pmatrix}b_1\\b_2\\\vdots\\b_n\end{pmatrix}-\begin{pmatrix}a_1\\a_2\\\vdots\\a_n\end{pmatrix}$

vector starting at origin and going a point is denoted with a vector of that point

Vector Operations

• scalar multiplication makes vector longer/shorter
• vector sum represents combined displacement
  • parallelogram rule shows parallelogram with $\vec{v}$, $\vec{w}$, $\vec{v}+\vec{w}$
    

---

Linear Surfaces

Lines

Line in $\mathbb{R}^2$ through $(1,2)$ and $(3,1)$ is comprised of vectors
$\left\{\begin{pmatrix}1\\2\end{pmatrix}+t\begin{pmatrix}2\\-1\end{pmatrix}\middle| t\in\mathbb{R}\right\}$
Vector associated with parameter $t$, $\begin{pmatrix}2\\-1\end{pmatrix}$, is a direction vector

Intuition

line through $A=(a_1,...,a_n)$ and $B=(b_1,...,b_n)$ is one point on the line (eg $A$) plus some multiple of the displacement vector (eg $B-A$)

Planes

Plane in $\mathbb{R}^3$ going through $(a_1,a_2,a_3)$, $(b_1,b_2,b_3)$, $(c_1,c_2,c_3)$ consists of
$\left\{\begin{pmatrix}a_1\\a_2\\a_3\end{pmatrix}+t\begin{pmatrix}b_1-a_1\\b_2-a_2\\b_3-a_3\end{pmatrix}+s\begin{pmatrix}c_1-a_1\\c_2-a_2\\c_3-a_3\end{pmatrix}\middle|t,s\in\mathbb{R}\right\}$

A set in the form $\left\{\vec{p}+t_1\vec{v}_1+t_2\vec{v}_2+\cdots+t_k\vec{v}_k\middle| t_1,t_2,...,t_k\in\mathbb{R}\right\}$ where $v_1,v_2,...,v_k\in\mathbb{R}^n$ and $k\le n$ is a $k$-dimensional linear surface or $k$-flat$\rightarrow$ multi-dimensional extension of lines and planes

---

Metrics

Length

length of $\vec{v}\in\mathbb{R}^n$ is
$|\vec{v}|=\sqrt{v_1^2+\cdots+v_n^2}$
Clearly, $|a\vec{v}|=|a||\vec{v}|$ for all $a\in\mathbb{R}$ and all $\vec{v}\in\mathbb{R}^n$ (note: $|-\vec{v}|=|\vec{v}|$)

normalize vector $\vec{v}$ to unit length by taking $\vec{v}/|\vec{v}|$

Dot Product

dot product or inner product or scalar product of two $n$-component vectors is the linear combination of the components:
$\vec{u}\cdot\vec{v}=u_1v_1+u_2v_2+\cdots+u_nv_n$
Properties:

1. $\vec{v}\cdot\vec{v}=|\vec{v}|^2$
2. $\vec{u}\cdot\vec{v}=\vec{v}\cdot\vec{u}$ for all $\vec{u},\vec{v}\in\mathbb{R}^n$ (symmetry)
3. $(a\vec{u})\cdot(b\vec{v})=ab(\vec{u}\cdot\vec{v})$ for all $a,b\in\mathbb{R}$ and all $\vec{u},\vec{v}\in\mathbb{R}^n$
4. $(\vec{u}_1+\vec{u}_2)\cdot(\vec{v}_1+\vec{v}_2)=\vec{u}_1\cdot\vec{v}_1+\vec{u}_1\cdot\vec{v}_2+\vec{u}_2\cdot\vec{v}_1+\vec{u}_2\cdot\vec{v}_2$ for all $\vec{u}_1,\vec{u}_2,\vec{v}_1,\vec{v}_2\in\mathbb{R}^n$
   3 and 4 together express bilinearity

Proofs

Property 1

$\vec{v}=\langle v_1,v_2,...,v_n\rangle\\ \vec{v}\cdot\vec{v}=\langle v_1,v_2,...,v_n\rangle\cdot\langle v_1,v_2,...,v_n\rangle\\ =v_1^2+v_2^2+\cdots+v_n^2=|\vec{v}|^2$

Property 2

$\vec{u}=\langle u_1,u_2,...,u_n\rangle,\vec{v}=\langle v_1,v_2,...,v_n\rangle\\ \vec{u}\cdot\vec{v}=u_1v_1+u_2v_2+\cdots+u_nv_n\\ =v_1u_1+v_2u_2+\cdots+v_nu_n=\vec{v}\cdot\vec{u}$

Property 3

$\vec{u}=\langle u_1,u_2,...,u_n\rangle,\vec{v}=\langle v_1,v_2,...,v_n\rangle\\ (a\vec{u})\cdot(b\vec{v})=\langle au_1,au_2,...,au_n\rangle\cdot\langle bv_1,bv_2,...,bv_n\rangle\\ abu_1v_1+abu_2v_2+\cdots+abu_nv_n\\ =ab(u_1v_1+u_2v_2+\cdots+u_nv_n)=ab(\vec{u}\cdot\vec{v})$

Property 4

$\vec{u}_1=\langle u_{1_1},...,u_{1_n}\rangle,\vec{u}_2=\langle u_{2_1},...,u_{2_n}\rangle,\\ \vec{v}_1=\langle v_{1_1},...,v_{1_n}\rangle,\vec{v}_2=\langle v_{2_1},...,v_{2_n}\rangle\\ (\vec{u}_1+\vec{u}_2)\cdot(\vec{v}_1+\vec{v}_2)=\langle u_{1_1}+u_{2_1},...,u_{1_n}+u_{2_n}\rangle\cdot\langle v_{1_1}+v_{2_1},...,v_{1_n}+v_{2_n}\rangle\\ =(u_{1_1}+u_{2_1})(v_{1_1}+v_{2_1})+\cdots+(u_{1_n}+u_{2_n})(v_{1_n}+v_{2_n})\\ =u_{1_1}v_{1_1}+u_{1_1}v_{2_1}+u_{2_1}v_{1_1}+u_{2_1}v_{2_1}+\cdots+u_{1_n}v_{1_n}+u_{1_n}v_{2_n}+u_{2_n}v_{1_n}+u_{2_n}v_{2_n}\\ =\vec{u}_1\cdot\vec{v}_1+\vec{u}_1\cdot\vec{v}_2+\vec{u}_2\cdot\vec{v}_1+\vec{u}_2\cdot\vec{v}_2$

---

Triangle Inequality

For any $\vec{u},\vec{v}\in\mathbb{R}^n$,
$|\vec{u}+\vec{v}|\le|\vec{u}|+|\vec{v}|$
with equality iff one vector is a nonnegative scalar multiple of the other
Proof later

Cauchy-Schwarz Inequality

For any $\vec{u},\vec{v}\in\mathbb{R}^n$
$\vec{u}\cdot\vec{v}\le|\vec{u\cdot}\vec{v}|\le|\vec{u}||\vec{v}|$
Equality $|\vec{u}\cdot\vec{v}|=|\vec{u}||\vec{v}|$ iff one vector is a scalar multiple of the other
Equality $\vec{u}\cdot\vec{v}=|\vec{u}||\vec{v}|$ iff one vector is a nonnegative scalar multiple of the other
$\vec{u}\cdot\vec{v}\le |\vec{u}\cdot\vec{v}|$ should be obvious

Proof of Cauchy-Schwarz

Let $\vec{u},\vec{v}\in\mathbb{R}^n$ and $t\in\mathbb{R}$.
By the trivial inequality, $|\vec{u}+t\vec{v}|^2\ge0$
Using properties of dot products and expanding,
$|\vec{u}+t\vec{v}|^2=(\vec{u}+t\vec{v})\cdot(\vec{u}+t\vec{v})=|\vec{u}|^2+2t\vec{u}\cdot\vec{v}+|\vec{v}|^2=|\vec{u}|^2-2t\vec{u}\cdot\vec{v}+t^2|\vec{v}|^2\ge0$
Now consider this as a quadratic equation in $t$. This implies there are $0$ or $1$ real roots, thus the discriminant is nonpositive:
$(2\vec{u}\cdot\vec{v})^2-4|\vec{u}|^2|\vec{v}|^2\le0$
Rearranging and simplifying gives
$|\vec{u}\cdot\vec{v}|\le|\vec{u}||\vec{v}|$
Case when one vector is a multiple of the other or either is $\vec{0}$ is trivial.

Proof of Triangle Inequality

Since all numbers are nonnegative, the inequality holds iff ifs square holds:
$|\vec{u}+\vec{v}|^2\le(|\vec{v}|+|\vec{u}|)^2$
Left hand side implies
$|\vec{u}|^2+2\vec{u}\cdot\vec{v}+|\vec{v}|^2$
Right hand side imples
$|\vec{u}|^2+2|\vec{u}||\vec{v}|+|\vec{v}|^2$
The inequality simplies to
$\vec{u}\cdot\vec{v}\le|\vec{u}||\vec{v}|$
This is true by Cauchy-Schwarz, so the Triangle Inequality must be true. By the equality condition of Cauchy-Schwarz, equality holds iff one vector is a nonnegative scalar multiple of the other.

---

Angles

Angle between $\vec{u},\vec{v}\in\mathbb{R}$ is:
$\theta=\arccos(\frac{\vec{u}\cdot\vec{v}}{|\vec{u}||\vec{v}|})$
Note: by Cauchy-Schwarz, the argument of $\arccos$ is between $-1$ and $1$

Consider triangle formed by $\vec{v},\vec{u},\vec{u-v}$
Use law of cosines and simplify

If $\theta=0$, $\vec{u}\parallel\vec{v}$ (parallel)
If $\theta=\pi/2$, $\vec{u}\perp\vec{v}$ (orthogonal)
If $\theta=\pi$, $\vec{u}\parallel\vec{v}$ in opposite directions
$\rightarrow$ Vectors from $\mathbb{R}$ are orthogonal iff their dot product is $0$

---

Relations and Partitions

return to Set Theory
relation between things (eg '$<$' or '$=$')
binary relation on set $A$ is a set of ordered pairs of elements of $A$

Examples

• the relation '$<$' on the integers include $(3,5)$, $(3,7)$, $(1,100)$
• the equality relation: $(1,1)$, $(2,2)$, etc
• the relation 'closer than 10': $\left\{(x,y)\middle||x-y|<10\right\}$

Equivalence Relation:
relation showing two objects are alike in some way
must satisfy:

• reflexivity: object is related to itself
• symmetry: if $a$ is related to $b$, $b$ is related to $a$
• transivity: if $a$ is related to $b$ and $b$ is related to $c$, $a$ is related to $c$

on the integers, '$=$' is an equivalence relation, '$<$' does not satisfy reflexivity or symmetry, 'nearer than 10' fails transitivity

Partitions

in the 'same sign' relation, three kinds of pairs:

• pairs of positives
• pairs of negatives
• pair of $0$
  Therefore, integers fall into exactly one of three classes: positive, negative, zero
  A partition of a set $\Omega$ is a collection of subsets $\{S_0,S_1,...\}$ s.t. every element of $\Omega$ is an element of a subset ($S_0\cup S_1\cup\cdots=\Omega$) and overlapping parts are equal (if $S_i\cap S_j\ne\empty$ then $S_i=S_j$)

Example

$\Omega-\left\{n/d\middle|n,d\in\mathbb{Z},d\ne0\right\}$
Define $S_{n,d}:\hat{n}/\hat{d}\in S_{n,d}\text{ if } \hat{n}d=n\hat{d}$
This partitions the set into equivalent fractions; i.e. "1/2" = "2/4"

Each part of a partition is an equivalence class, from which one is sometimes picked to be the class representative called canonical representative if there is some natural scheme (eg simplest/reduced form of a fraction)

Summary Section:

• binary relation: subset $R$ of set $A\times A$
  • instead of $(x,y)\in R$, write $x\sim_R y$ or $x\sim y$ and say "$x$ is related to $y$ for the relation $R$"
  • reflexive: $x\sim x$ for all $x\in A$
  • symmetric: if $x\sim y$ then $y\sim x$
  • transitive: if $x\sim y$ and $y\sim z$, then $x\sim z$
• binary relation satisfying reflexivity, symmetry, and transitivity is an equivalence relation
• a partition of a set $A$ is a collection of disjoint subsets whose union is $A$

---

Gauss-Jordan Reduction

extension of Gauss's Method

Instead of using back substitution from echelon form, make leading coefficients $1$ and continue to use row operations to eliminate upwards- reduced row echelon form

(all columns with a pivot are canceled)

Example

Solve the following system of equations
$3x-2y+z=7\\x+y-3z=-6\\2x-2y-3z=-7$

---

The resulting augmented matrix is
$\left(\begin{array}{ccc|c}3&-2&1&7\\1&1&-3&-6\\2&-2&-3&-7\end{array}\right)$
First get it to echelon form
$\xrightarrow{\rho_1\leftrightarrow\rho_2}\left(\begin{array}{ccc|c}1&1&-3&-6\\3&-2&1&7\\2&-2&-3&-7\end{array}\right)\xrightarrow[-2\rho_1+\rho_3]{-3\rho_1+\rho_2}\left(\begin{array}{ccc|c}1&1&-3&-6\\0&-5&10&25\\0&-4&3&5\end{array}\right)\xrightarrow{-4/5\rho_2+\rho_3}\left(\begin{array}{ccc|c}1&1&-3&-6\\0&-5&10&25\\0&0&-5&-15\end{array}\right)$
Next, make the leading coefficients 1
$\xrightarrow[-1/5\rho_3]{-1/5\rho_2}\left(\begin{array}{ccc|c}1&1&-3&-6\\0&1&-2&-5\\0&0&1&3\end{array}\right)$
Finally, use the pivots to clear out each row
$\xrightarrow[2\rho_3+\rho_2]{3\rho_3+\rho_1}\left(\begin{array}{ccc|c}1&1&0&3\\0&1&0&1\\0&0&1&3\end{array}\right)\xrightarrow{-\rho_2+\rho_1}\left(\begin{array}{ccc|c}1&0&0&2\\0&1&0&1\\0&0&1&3\end{array}\right)$
This shows the solution is
$\begin{pmatrix}x\\y\\z\end{pmatrix}=\begin{pmatrix}2\\1\\3\end{pmatrix}$

pivoting on an entry: using the entry to clear out the rest of a column (eg using bottom row $z$ to clear out all other $z$)

"Reduces to" is an equivalence
matrix $A$ reduces to matrix $B$ if $B$ is obtained from $A$ using successive elementary row operations given by Gauss's Method

Proof of Equivalence

Reflexivity: a matrix reduces to itself if you apply no operators, so $A\sim A$ Symmetry: if $A$ reduces to $B$, then $B$ can be reduced to $A$ by applying the opposite of the row operations: swapping can be reversed by swapping again rescaling by a factor of $k$ can be reversed by rescaling by a factor of $1/k$ row combination can be reversed by subtracting if added or adding if subtracted Transitivity: if $A$ reduces to $B$ after a set of row operations and $B$ reduces to $C$ after a set of row operations, then $A$ reduces to $C$ after the combined set of row operations Thus, all three conditions are satisfied, and "reduces to" is an equivalence

$\rightarrow$ matrices that reduce to each other are row equivalent

Linear Combination Lemma

Reduction steps (Gauss's method) takes linear combinations of the rows
A linear combination of linear combinations is a linear combination

Proof

Given set $c_{1,1}x_1+\cdots+c_{1,n}x_n$ through $c_{m,1}x_1+\cdots+c_{m_n}x_n$, consider linear combination
$d_1(c_{1,1}x_1+\cdots+c_{1,n}x_n)+\cdots+d_m(c_{m,1}x_1+\cdots+c_{m,n}x_n)$
this can be rearranged to
$(d_1c_{1,1}+\cdots+d_mc_{m,1})x_1+\cdots+(d_1c_{1,n}+\cdots+d_mc_{m,n})x_n$
which is a linear combination

This implies each row in a reduced matrix is a linear combination of the rows of the first

Proof Outline

Use induction. The base step is $0$ steps.
Assume everything after $k$ steps is a linear combination, then show $k+1$ must still be a linear combiantion after any of the three moves.
Essentially, show linear combination $\rightarrow$ linear combination after any of the steps.

In short: Gauss's method takes linear combinations of the rows to eliminate any linear relationship amont them

Reduced echelon form is unique
Two row equivalent matrices will yield the same reduced echelon form matrix
$\rightarrow$ it is the canonical form